#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}
//三数取中
int GetMidIndex(int* a, int left, int right)
{
	int mid = left + (right - left) / 2;
	if (a[left] < a[right])
	{
		if (a[mid] < a[left])
		{
			return mid;
		}
		else if (a[mid] > a[right])
		{
			return right;
		}
		else
		{
			return mid;
		}
	}
	else if (a[left] > a[right])
	{
		if (a[mid] > a[left])
		{
			return left;
		}
		else if (a[mid] < a[right])
		{
			return right;
		}
		else
		{
			return mid;
		}
	}
	else
	{
		return left;
	}
}

int Partition1(int* a,int left,int right)
{
	int mid = GetMidIndex(a, left, right);
	Swap(&a[left], &a[mid]);
	int keyi = left;
	while (left < right)
	{
		while (a[right] >= a[keyi] && right > left)
		{
			right--;
		}
		while (a[left] <= a[keyi] && left < right)
		{
			left++;
		}
		if(left < right)
			Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	return left;
}

//挖坑法
int Partition2(int* a, int left, int right)
{
	int mid = GetMidIndex(a, left, right);
	Swap(&a[left], &a[mid]);
	int key = a[left];
	int pivot = left;
	while (left < right)
	{
		while (a[right] >= key && right > left)
		{
			right--;
		}
		a[pivot] = a[right];
		pivot = right;
		while (a[left] <= key && left < right)
		{
			left++;
		}
		a[pivot] = a[left];
		pivot = left;
	}
	a[pivot] = key;
	return pivot;
}

//前后指针法
int Partition3(int* a, int left, int right)
{
	int mid = GetMidIndex(a, left, right);
	Swap(&a[left], &a[mid]);
	int keyi = left;
	int prev = left;
	int cur = left+1;
	while (cur <= right )
	{
		while (a[cur] >= a[keyi] && cur <= right)
		{
			cur++;
		}
		if (cur <= right )
		{
			prev++;
			Swap(&a[cur], &a[prev]);
			//换完cur一定要往前跑，不然会待在原地
			cur++;
		}
	}
	Swap(&a[prev], &a[left]);
	return prev;
}

void QuickSort(int* a,int left,int right)
{
	if (left > right)
	{
		return;
	}
	int keyi = Partition3(a,left,right);
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi+1, right);
}

void test()
{
	int n = 50000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand((unsigned)time(NULL));
	if (a == NULL)
	{
		perror("malloc");
	}
	for (int i = 0; i < n; i++)
	{
		a[i] = rand() % 1000000;
	}
	//int a[] = { 9,8,7,6,5,4,3,2,1 };
	int time1 = clock();
	QuickSort(a, 0, n - 1);
	int time2 = clock();
	printf("花费时间：%dms\n", time2 - time1);
	time1 = clock();
	QuickSort(a, 0, n - 1);
	time2 = clock();
	printf("花费时间：%dms\n", time2 - time1);
	free(a);
	/*for (int i = 0; i < 9; i++)
	{
		printf("%d ", a[i]);
	}*/
}
int main()
{
	test();
	return 0;
}